Позициони запис - вредност и цифре
Раније смо се већ упознали са основним дефиницијама позиционог записа и видели смо да су две основне операције израчунавање вредности броја на основу познатих цифара и израчунавање цифара датог броја.
Цифре у запису броја \(x\) у основи \(b\) се могу добити тако што се примењује низ корака таквих да се у сваком кораку одређује и брише цифра јединица броја. Обратимо пажњу на то да се у овом итеративном поступку број коме се одређују цифре стално мења. Цифру \(c_0\) у запису броја \(x = c_n\cdot b^n + \ldots c_1\cdot b + c_0\) можемо одредити као \(x \,\mathrm{mod}\,b\), а важи да је \(x \,\mathrm{div}\,b = c_n\cdot b^{n-1} + \ldots + c_2 \cdot b + c_1\). Ако се сада број \(x\) замени вредношћу \(x \,\mathrm{div}\,b\), цифру \(c_1\) добијамо као остатак при дељењу са \(b\), док је количник при дељењу са \(b\) једнак \(c_n b^{n-2} + \ldots + c_3 \cdot b + c_2\). Када се поступак настави на потпуно исти начин, можемо издвојити цифру \(c_2\), затим \(c_3\) и тако даље. Цифре, дакле, добијамо поступком наредног облика.
c0 = x % b; x = x / b;
c1 = x % b; x = x / b;
...Вредност броја се најједноставније одређује Хорнеровом схемом, кренувши од цифре највеће тежине, па уназад до цифара јединица. Подсетимо се, по Хорнеровој схеми вредност броја једнака је \((\ldots ((c_n \cdot b + c_{n-1})\cdot b + c_{n-2})\cdot b + \ldots + c_1)\cdot b + c_0\). У итеративном поступку вредност иницијализујемо на нулу, а затим је у сваком кораку множимо основом \(b\) и додајемо наредну цифру. Вредност, дакле, одређујемо итеративним поступком наредног облика.
x = 0;
x = x * b + c[n];
x = x * b + c[n-1];
...
x = x * b + c[0];Приметимо и да је број могао бити иницијализован на вредност \(c_n\) након чега би се до резултата стизало у једном кораку мање.
Индукцијом се лако може доказати да је након \(k\) корака вредност променљиве \(x\) једнака броју \((c_n\ldots c_{n-k+1})_b\) који се добија од првих \(k\) цифара тј. \(c_n\cdot b^{k-1} + c_{n-1}\cdot b^{k-2} + \ldots + c_{n-k+1}\).
На пример, за вредности цифара \(1\), \(2\)
и \(3\), променљива x
имаће редом вредности \(0, 1, 12,
123\).
Итеративни поступак у ком вредност одређујемо на основу вредности цифара кренувши од цифре најмање тежине захтева да се поред вредности броја одржава и тежина наредне цифре, тј. текући степен основе (њега иницијализујемо на 1 и множимо га основом у сваком кораку).
x = 0; tezina = 1;
x = x + tezina * c[0]; tezina = tezina * b;
x = x + tezina * c[1]; tezina = tezina * b;
...Индукцијом се лако може доказати да ће након \(k\) корака променљива x имати
вредност једнаку броју \((c_{k-1}\ldots
c_{0})_b\) који се добије од последњих \(k\) цифара, док ће променљива
tezina имати вредност \(10^k\).
На пример, за вредности цифара \(1\), \(2\)
и \(3\), променљива x
имаће редом вредности \(0, 3, 23,
123\).
Приметимо да Хорнерова шема не захтева израчунавање степена основе, што је за дуже бројеве чини ефикаснијом од класичног поступка.
Позициони запис - вредност и цифре
Раније смо се већ упознали са основним дефиницијама позиционог записа и видели смо да су две основне операције израчунавање вредности броја на основу познатих цифара и израчунавање цифара датог броја.
Цифре у запису броја \(x\) у основи \(b\) се могу добити тако што се примењује низ корака таквих да се у сваком кораку одређује и брише цифра јединица броја. Обратимо пажњу на то да се у овом итеративном поступку број коме се одређују цифре стално мења. Цифру \(c_0\) у запису броја \(x = c_n\cdot b^n + \ldots c_1\cdot b + c_0\) можемо одредити као \(x \,\mathrm{mod}\,b\), а важи да је \(x \,\mathrm{div}\,b = c_n\cdot b^{n-1} + \ldots + c_2 \cdot b + c_1\). Ако се сада број \(x\) замени вредношћу \(x \,\mathrm{div}\,b\), цифру \(c_1\) добијамо као остатак при дељењу са \(b\), док је количник при дељењу са \(b\) једнак \(c_n b^{n-2} + \ldots + c_3 \cdot b + c_2\). Када се поступак настави на потпуно исти начин, можемо издвојити цифру \(c_2\), затим \(c_3\) и тако даље. Цифре, дакле, добијамо поступком наредног облика.
c0 = x % b; x = x / b;
c1 = x % b; x = x / b;
...Вредност броја се најједноставније одређује Хорнеровом схемом, кренувши од цифре највеће тежине, па уназад до цифара јединица. Подсетимо се, по Хорнеровој схеми вредност броја једнака је \((\ldots ((c_n \cdot b + c_{n-1})\cdot b + c_{n-2})\cdot b + \ldots + c_1)\cdot b + c_0\). У итеративном поступку вредност иницијализујемо на нулу, а затим је у сваком кораку множимо основом \(b\) и додајемо наредну цифру. Вредност, дакле, одређујемо итеративним поступком наредног облика.
x = 0;
x = x * b + c[n];
x = x * b + c[n-1];
...
x = x * b + c[0];Приметимо и да је број могао бити иницијализован на вредност \(c_n\) након чега би се до резултата стизало у једном кораку мање.
Индукцијом се лако може доказати да је након \(k\) корака вредност променљиве \(x\) једнака броју \((c_n\ldots c_{n-k+1})_b\) који се добија од првих \(k\) цифара тј. \(c_n\cdot b^{k-1} + c_{n-1}\cdot b^{k-2} + \ldots + c_{n-k+1}\).
На пример, за вредности цифара \(1\), \(2\)
и \(3\), променљива x
имаће редом вредности \(0, 1, 12,
123\).
Итеративни поступак у ком вредност одређујемо на основу вредности цифара кренувши од цифре најмање тежине захтева да се поред вредности броја одржава и тежина наредне цифре, тј. текући степен основе (њега иницијализујемо на 1 и множимо га основом у сваком кораку).
x = 0; tezina = 1;
x = x + tezina * c[0]; tezina = tezina * b;
x = x + tezina * c[1]; tezina = tezina * b;
...Индукцијом се лако може доказати да ће након \(k\) корака променљива x имати
вредност једнаку броју \((c_{k-1}\ldots
c_{0})_b\) који се добије од последњих \(k\) цифара, док ће променљива
tezina имати вредност \(10^k\).
На пример, за вредности цифара \(1\), \(2\)
и \(3\), променљива x
имаће редом вредности \(0, 3, 23,
123\).
Приметимо да Хорнерова шема не захтева израчунавање степена основе, што је за дуже бројеве чини ефикаснијом од класичног поступка.